\documentclass[9pt]{beamer}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{url}
%\usetheme{Berkeley}
\usetheme{Copenhagen}

\pgfdeclareimage[height=0.5cm]{logo}{./imagens/positivo_cor}
\logo{\pgfuseimage{logo}} 

\title{Estudos em Criptografia}

\author{Prof. MSc. João José Costa Gondim}
\institute[UnB]{Instituto de Exatas\\Departamento de Ciência da
  Computação\\Universidade de Brasília}

\begin{document}
\begin{frame}
	\titlepage
\end{frame}

\section{Introdução}

\subsection{Criptografia Básica x Criptografia Moderna}
\frame{
  \frametitle{Arte X Ciência}
  \begin{itemize}
      \item Historicamente, a criptografia era vista como uma arte. \\
     \vfill
      \item Cifras elaboradas de maneira \emph{ad-hoc} e avaliadas de modo empírico.\\
     \vfill 
      \item Atualmente, todas estas cifras \emph{ad-hoc} (Cesar, Vigènere, Deslocamento) podem ser
	  facilmente quebradas.\\ 
      \vfill
      \item Necessidade de maior formalismo, fazendo com que a criptografia passe a ser vista como ciência.\\
     \vfill 
     \end{itemize}
}

\section{Criptografia Moderna}

\subsection{Princípios Básicos}
\frame{
  \frametitle{Criptografia Moderna}
  \begin{itemize}
       \item Como ciência, existe a esperança da criptografia colocar fim no ciclo: cifra elaborada, cifra quebrada. \\
         \vfill
        \item Muitas diferenças entre criptografia moderna e clássica, em especial três princípios:
	\begin{itemize}
	  \vfill
	  \item Princípio 1 - Formular definição precisa e rigorosa de segurança.\\
	  \vfill
	  \item Princípio 2 - Quando a segurança está baseada em uma premissa não provada, esta
	  deve ser bem enunciada, e o mais simples possível.\\
	  \vfill
	  \item Princípio 3 - Protocolos criptográficos devem ser acompanhados de provas rigorosas de
	  segurança, no que tange a definição de segurança elaborada em consonância com o princípio 1, e
          de acordo com as premissas enunciadas conforme o princípio 2 (Se uma premissa for necessária). \\
	\end{itemize}
    \end{itemize}
}

\subsection{Princípio 1 - Definição Rigorosa de Segurança}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
       \item Segundo a criptografia moderna, uma definição formal de segurança é um pré-requisito essencial para projeto,
	  uso e estudo de qualquer primitiva ou protocolo criptográfico. Seguem diversos aspectos que visam exemplificar a 
	  importância de uma definição formal.
        \vfill
	  \item A ausência de definição formal implica na falta de métrica para saber se o objetivo foi alcançado (Projeto).\\
	  \vfill
	  \item Não há muita possibilidade de direcionamento de esforços no sentido em que não se sabe precisamente 
	  o objetivo vislumbrado (Projeto).\\
	  \vfill
	  \item Risco de se utilizar uma solução segura demais, no entanto menos eficiente (Projeto).\\
	  \vfill
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
       \item Como escolher qual esquema criptográfico utilizar ? (Uso)
        \vfill
        \item Dado um esquema, ele atinge as minhas expectativas de segurança ? (Uso)
         \vfill
	\item Se definida formalmente a minha necessidade de segurança, bem como a oferecida pelo esquema dado,
	  seria possível verificar se tal esquema atende minhas necessidades. (Uso)
	  \vfill
	\item O ideal é que o esquema atenda a minha necessidade, mas sem ser muito mais seguro do que isso, 
	o que implicaria ineficiência. (Uso)
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
       \item Como comparar dois esquemas ? (Estudo)
        \vfill
        \item Sem definição formal de segurança resta apenas a eficiência como métrica. No entanto, a
	eficiência isoladamente não é uma boa métrica, uma vez que um sistema muito eficiente pode ser
	bastante inseguro. (Estudo)
         \vfill
	\item Se definida formalmente a minha necessidade de segurança, bem como a oferecida pelo esquema dado,
	  seria possível verificar se tal esquema atende minhas necessidades. (Estudo)
	  \vfill
	\item Vale ainda ressaltar a maior facilidade de compreensão do \emph{trade-off} entre eficiência e segurança, uma 
          vez que se tenha uma definição formal da última. (Estudo)
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
       \item Além de todas as vantagens já explicadas, a existência de uma definição formal de segurança possibilita
	que um esquema seja verificado matematicamente.
        \vfill
        \item Pode-se pensar que a definição de segurança é trivial ou intuitiva. No entanto, serão apresentadas algumas 
	definições intuitivas e seus problemas.
         \vfill
	\item Definição 1: Um esquema é seguro, se dado um texto cifrado, o adversário não consegue achar a chave.
	  \vfill
	\item Problema: Segundo essa definição, um esquema seria considerado seguro ainda que um adversário descobrisse
	  o texto em claro desde que ele não descubra a chave.
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Definição 2: Um esquema é seguro, se nenhum adversário conseguir obter o texto em claro, a partir do
	  texto cifrado.
	  \vfill
	\item Problema:  Segundo essa definição, um esquema seria considerado seguro ainda que um adversário consiga 
	  obter 90\% do texto em claro. Isto é um problema, por exemplo, em contratos onde o que mais
	  interessa ao adversário são os números.
	  \vfill
	\item Definição 3:  Um esquema é seguro, se nenhum adversário conseguir obter algum caracter do texto em claro,
	  a partir do texto cifrado.
	  \vfill
	\item Problema: Ainda no exemplo do contrato, o adversário poderia descobrir um limite inferior e/ou superior 
	  para um determinado valor que conste no contrato, o que não viola a definição de segurança.
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Definição 4: Um esquema é seguro, se nenhum adversário conseguir obter alguma informação significativa do texto em claro,
	  a partir do texto cifrado.
	  \vfill
	\item Problema: Há a necessidade de se definir o que é uma informação significativa, além do fato de que definições de segurança
	  devem valer para todas potenciais aplicações existentes.
	  \vfill
	\item Definição 5: Um esquema é seguro, se nenhum adversário consegue computar alguma função relativa ao texto em claro, 
	  a partir do texto cifrado.
	  \vfill
	\item Essa última definição é considerada correta, muito embora seja desejável especificar mais algumas características do adversário.
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Uma definição de segurança deve levar em conta principalmente dois conceitos:
	  \vfill
       \item O que é uma quebra ?
	%    \vfill

	\begin{itemize}
	    \item Esta questão é resolvida pelas diversas definições de segurança apresentadas nos slides anteriores.
	    \vfill
	\end{itemize}
	\item Qual o poder do adversário ?
	%    \vfill
	  \begin{itemize}
	   \item O poder do adversário é relativo a que tipo de ataques ele pode realizar (ataque somente ao texto cifrado ou ataque de texto em claro escolhido) e a seu poder computacional, que 
	  em geral é considerado polinomial.
	\end{itemize}
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Em geral, toda definição de segurança tem o seguinte formato:
	  \vfill
	\begin{center}
	Um esquema criptográfico é seguro para determinada tarefa se nenhum adversário de poder especificado pode
	  conseguir uma quebra especificada.
	  \vfill
	\end{center}
	\item Vale ressaltar que não é recomendável tentar antever as estratégias do adversário quando do projeto de um esquema criptográfico.
	\vfill
	\item Sobre o adversário, o importante é saber o seu ``poder'', e não como ele vai usá-lo.
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item A partir de uma definição de segurança, é possível formulá-la matematicamente. Tal definição deve ser precisa, isto é
	  não subestimando o real ``poder'' do adversário e nem definindo de maneira imprecisa uma quebra.
	  \vfill
	\item 
	  Um erro na definição de segurança faz com que mesmo um esquema provado matematicamente como satisfazendo a definição
	  se torne inútil nesta situação.
	  \vfill
	\item É possível uma definição de segurança bem aceita ser mal adaptada para outra aplicação, 
	  fazendo com que a definição para esta aplicação tenha que ser refinada.
	  \vfill
	\item Por exemplo, em \emph{smart-cards} há de se levar em consideração que
	  o consumo de energia pode dar ao adversário informações sobre a chave.
    \end{itemize}
}

\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Esta dificuldade em modelar matematicamente situações do cotidiano não se restringe apenas a criptografia, 
	    ocorrendo também em outras ciências.
	  \vfill
	\item Pode se fazer uma analogia com a computabilidade, onde é difícil expressar matematicamente o significado 
	  de um problema ser computável.
	  \vfill
	\item Alan Turing utiliza argumentos da seguinte natureza para dizer se um processo é computável:
	  Intuitivos, baseados em provas de equivalência e exemplos de problemas mais ``difíceis''.
	  \vfill
	\item Quando um criptógrafo deseja se convenver de que determinada definição de
	  segurança realmente é útil para o cotidiano,
	  ele também se apóia em idéias da mesma natureza das que Turing utilizou.
    \end{itemize}
}
	
\frame{
  \frametitle{Definição Formal de Segurança}
  \begin{itemize}
	\item Uma definição de segurança deve atender ao menos a idéia intuitiva de segurança que 
	  em geral é pouco rigorosa.
	  \vfill
	\item Existe a possibilidade de se justificar uma definição de segurança, mostrando que ela é equivalente ou mais abrangente
	  que uma definição mais velha, mais familiar e/ou mais intuitiva.
	  \vfill
	\item Pode-se ainda avaliar uma definição de segurança mostrando que os diversos exemplos de ataques
	conhecidos são descartados pela definição proposta.
	  \vfill
	\item Há ainda o ``teste do tempo'', uma vez que quanto mais velha a definição, mais averiguada minunciosamente por 
	  pesquisadores e profissionais ela foi.
	  \vfill
    \end{itemize}
}

\subsection{Princípio 2 - Enunciado Preciso das Premissas}

\frame{
  \frametitle{Enunciado das Premissas}
  \begin{itemize}
      \item A maioria dos esquemas criptográficos se utiliza de alguma premissa em sua prova, principalmente premissas relacionadas 
	 à complexidade computacional.
      \vfill 
       \item O segundo princípio básico da criptografia afirma que é necessário enunciar detalhadamente as premissas por 3
	  motivos: 
         \vfill
        \begin{itemize}
	  \item Validação da premissa;
	     \vfill
	  \item Comparação de esquemas;
	    \vfill
	  \item Facilitar as provas de segurança.
        \end{itemize}
       \end{itemize}
}

\frame{
  \frametitle{Validação da Premissa}
  \begin{itemize}
      \item As premissas em geral não são provadas, mas são como conjecturas assumidas como verdadeiras.
      \vfill
       \item Para possiblitar o estudo de uma premissa é necessário que esta seja bem enunciada.
        \vfill
       \item O estudo possibilita que a premissa seja refutada ou que se verifique que uma outra conjectura 
	 implica na premissa.
	\vfill
      \item É possível concluir que um enunciado preciso
	de uma premissa aumenta a sua confiabilidade por esta estar exposta ao crivo de refutação dos pesquisadores e profissionais.
  \end{itemize}
}

\frame{
  \frametitle{Comparação de Esquemas}
  \begin{itemize}
      \item Supondo dois esquemas baseados em premissas igualmente eficientes, como compará-los ?
	\vfill
       \item Se $Esquema \ A \ \Rightarrow \ Esquema \ B$, então é preferível escolher o $Esquema \ B$, pois mesmo que $A$ seja falso,
	 $B$ pode ser verdadeiro.
        \vfill
       \item Se as premissas utilizadas pelos 2 esquemas forem incomparáveis, é recomendável utilizar o esquema que possui a premissa
	mais estudada ou a mais simples.
  \end{itemize}
}

\frame{
  \frametitle{Facilitar as Provas de Segurança}
  \begin{itemize}
      \item Em geral, esquemas de criptografia moderna são apresentados juntamente a uma prova de segurança.
      \vfill
       \item Se a segurança do esquema não puder ser provada incodicionalmente, ela se baseia em uma premissa.
        \vfill
       \item Então a prova, só pode ser concluída caso haja uma definição precisa da premissa daquele esquema.
	\vfill
	\item É interessante ter uma premissa simples, uma vez que esta foi mais estudada e pode
	  servir de base para mais de um esquema criptográfico.
  \end{itemize}
}

\subsection{Princípio 3 - Prova Rigorosa de Segurança}

\frame{
  \frametitle{Verificação de Segurança}
  \begin{itemize}
      \item Os dois princípios anteriores possibilitam a verificação matemática da segurança de um esquema. Porque é necessária uma prova tão rigorosa ?
	\vfill
	\begin{itemize}
       \item Sem a prova de segurança de um esquema para determinados adversários e quebras, este esquema se torna refém 
	da intuição de seu autor.
	\vfill
	\item A experiência mostra que muitos esquemas intuitivos foram quebrados, seja depois de poucos ou muitos anos
	após sua proposição.
	\vfill
	\item Uma quebra é potencialmente muito ``cara''. Imagine, por exemplo, a quebra de um esquema
	  de criptografia de um banco.
	\vfill
\end{itemize}
	\item Portanto, uma prova de segurança não é apenas desejável, é \textbf{necessária}.
	
  \end{itemize}
}

\frame{
  \frametitle{Abordagem de Verificação}
  \begin{itemize}
      \item Em geral, as provas de esquemas de segurança utilizam uma abordagem reducionista.
	\vfill
      \item Essa abordagem, consiste em provar teoremas tais como: $Premissa \ P \ \Rightarrow \ Esquema \ A \ Seguro$.
	\vfill
      \item Uma vez que provado este teorema, para o $Esquema \ A$ não ser seguro obrigatoriamente a $Premissa \ P$ será falseável.
	\vfill
      \item Além disso as premissas escolhidas normalmente são muito difíceis de serem falseadas, o que torna complexo achar 
	uma instância onde o $Esquema \ A$ seja inseguro.
  \end{itemize}
}

\subsection{Conclusão}

\frame{
  \frametitle{Conclusão}
  \begin{itemize}
      \item A combinação dos 3 princípios apresentados constitui uma abordagem rigorosa para a criptografia que é distinta 
	da abordagem \emph{ad-hoc} da criptografia clássica.
	\vfill
      \item A abordagem \emph{ad-hoc} pode infringir um dos três princípios, mas frequentemente infringe os três.
	\vfill
      \item No entanto, a abordagem \emph{ad-hoc} ainda é muito utilizada por quem deseja uma solução simples e rápida, no entanto
	menos segura.
  \end{itemize}
}

\nocite{katz}

\section{Referências}
\frame{
\frametitle{Referências}
  \bibliographystyle{plain}
  \bibliography{bibliografia}
}

\end{document}
